With the advance of ultra deep submicron technology, manufacturability has become one of the major problems in very large scale integrated (VLSI) circuit design. Because the ability to control the physical properties of fabricated devices and interconnects is decreasing, the variability of finally printed shapes and their physical properties is increasing. Therefore, design for manufacturability (DFM) has become one of the most challenging topics among designers and researchers. Post-layout manufacturability enhancement techniques, such as optical proximity correction (OPC) and resolution enhancement techniques (RET), have been a key step to compensate for shape variation and ensure the manufacturability of designs. However, these post-layout processes are very expensive. The complexity of these techniques is increasing as well. For the emerging technologies (65 nm and beyond), the computation cost and complexity of the post-layout processes are becoming the bottle-necks in the design-to-silicon flow.
Therefore, regular layout styles have been proposed to improve the manufacturability and achieve manageable post-layout processing complexity. However, pursuit of regular layout styles has caused chip layout to become subject to complex rules governing, among other things, the size, shape, and location of objects on process layers. Compliance with these rules is important to ensure chip functionality and manufacturability.
A conventional shape-based layout includes a set of polygons, each of which is associated with a layer, including diffusion, polysilicon (poly), metals, contact, vias, etc. Layouts can be flat or hierarchical and, as described above, may be subject to design ground rules to ensure manufacturability. Typically, ground rules include spacing rules specifying the minimum space between objects, length rules specifying the minimum length of some objects, width rules specifying the minimum width of some objects, and methodology rules specifying the design requirement for assembling cells.
An effective methodology in pursuing regular layout styles to deal with computation cost and complexity of post-layout process is to impose restrictive design rules (RDRs) which require layout objects to be placed at a set of pitch grids. Such restrictive design rules are also called grid constraints. Grid constraints require that a specified portion of an object be located on a grid that is defined on the layout. A layout may have single or multiple grid constraints.
Techniques for designing layouts that comply with ground rules and grid constraints include compaction and minimum layout perturbation-based legalization. Usually they are performed in two successive steps, first in X direction and then in Y direction, or vice versa, in order to obtain a legalized solution to a two-dimensional layout. The compaction technique which is based on the longest path computation minimizes the area of the layout by relocating objects while satisfying rules and constraints. However, so far the compaction technique does not handle the multiple grid constraints for a hierarchical layout. Furthermore, when grid constraints is taken into account, the iteration bound which is used to check whether there is a feasible compaction solution for a flat layout to satisfy the given constraints (e.g., whether there is a positive cycle in the grid longest path) is not accurate.
The minimum layout perturbation-based legalization technique is an alternative to compaction. The minimum layout perturbation-based legalization technique is described in U.S. Pat. No. 6,189,132, the disclosure of which is hereby incorporated by reference in its entirety. The minimum layout perturbation-based legalization technique attempts to improve a given layout by correcting ground rule violations while changing the original layout as little as possible. The minimum layout perturbation-based legalization technique is advantageous because it addresses cases with conflicting rules that cause positive cycles and which cannot be handled by longest path-based compaction techniques. The minimum layout perturbation-based legalization technique does not consider grid constraints.
Accordingly, there exists a need in the art to overcome the deficiencies and limitations described hereinabove.